The invention relates to the field of computerized encrypted storage.
Outsourcing data storage to remote servers is an extremely useful technology that has been adopted both by large organizations and by individual users. It offers great benefits, but at the same time, raises various concerns when dealing with sensitive data. In particular, in order to preserve the confidentially of the data against an untrusted server, user-side symmetric encryption methods are typically employed prior to storing the data. As a result, operations as basic as keyword searches become computationally-expensive and sometimes even infeasible. This problem has motivated the cryptographic community to develop encryption methods that enable to search over symmetrically-encrypted data while not revealing sensitive information.
Searchable symmetric encryption (SSE) is a mechanism that allows a client to store data on an untrusted server and later perform keyword searches. See, for example, D. X. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In Proceedings of the 21st Annual IEEE Symposium on Security and Privacy, pages 44-55, 2000. In SSE, given a keyword w, the client should be able to retrieve all documents that contain w. First, the client encrypts its database and uploads it to the server. The client can then repeatedly query the server with various keywords. Informally, the security requirement asks that the server does not learn any information about keywords for which the client did not issue any queries.
A very productive line of research has been devoted to the construction of searchable symmetric encryption schemes. However, implementations and experiments with real-world databases oftentimes indicate that the performance of the known schemes is quite disappointing and scales badly to large databases. See, for example, D. Cash, S. Jarecki, C. S. Jutla, H. Krawczyk, M. Rosu, and M. Steiner. Highly-scalable searchable symmetric encryption with support for boolean queries. In Advances in Cryptology—CRYPTO '13, pages 353-373, 2013. Somewhat surprisingly, it turns out that the main bottleneck is in fact not the cryptographic processing of the data, but rather lower-level issues resulting from the inefficient memory layouts required by these schemes.
The foregoing examples of the related art and limitations related therewith are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent to those of skill in the art upon a reading of the specification and a study of the figures.